// 输入n，请设计算法能以从小到大的顺序找回第n个丑数。
// （丑数指能满足：2的x次方乘3的y次方乘5的z次方的形式，x、y、z可以为0）

var nthUglyNumber: (n: number) => number = function (n) {
    // 第一个丑数是1、声明dp数组和三个指针
    let dp: number[] = [1];
    let pointer2: number = 0;
    let pointer3: number = 0;
    let pointer5: number = 0;
    // 对dp数组进行遍历
    for (let i: number = 1; i < n; i++) {
        // 条件转移方程：根据状态变量来计算出下一个丑数
        dp[i] = Math.min(dp[pointer2] * 2, dp[pointer3] * 3, dp[pointer5] * 5);
        // 三者之间需要分别独立维护，因为在一轮计算中可能同时更新2-3个指针
        if (dp[i] === dp[pointer2] * 2) {
            pointer2++;
        } if (dp[i] === dp[pointer3] * 3) {
            pointer3++;
        } if (dp[i] === dp[pointer5] * 5) {
            pointer5++;
        }
    }
    // 返回dp数组的最后一位即为结果
    return dp[dp.length - 1];
};

// 这道题采用的是动态规划算法和数学递推求解...我个人觉得还是很难想的
// 首先根据丑数的定义，我们可以知道任意的丑数，它乘三、乘五、乘二以后的结果肯定还是丑数
// 所以当前要求的第n个丑数，它也是由某个丑数乘2、3、5得来的
// 我们这里定义一个动态规划数组dp，dp的第i项表示第i个丑数
// 但难点在于丑数从小到大的递推过程中是没有直观数学规律可寻的，这也是我觉得比较棘手的地方
// 这里我们定义三个状态变量（实际上是数组索引指针），p2\p3\p5分别表示当前dp结果除以2\3\5时指向的下标
// 然后我们可以寻找条件转移方程,对dp数组基于n进行循环
// 在循环过程中，每次选取 2 * p2、3 * p3 和 5 * p5 这三个数中结果最小的数，
// 并且将对应的指针向前移动。有效循环是 n 次，当循环结束后，dp数组中就按从小到大的顺序保存了丑数。
// 在这里又有一个比较困难的地方，就是在维护p2\p3\p5指针的过程中，
// 这三个指针是彼此独立的，在一轮计算中可能需要同时更新2-3个指针
// 原因是例如 6 = 2*3这种，需要同时更新p2\p3才是正确的